public class BTree {

    public static int M = 3;//几叉树

    static class Node {
        int[] key; //关键字
        Node[] subs; //孩子域
        Node parent;//双亲结点
        int useSized;//使用的空间数量

        public Node() {
            //多加一个区域，是为了便于后续的分裂
            key = new int[M];
            subs = new Node[M+1];
        }
    }

    Node root;//根结点

    public void insert(int key) {
        Node node = new Node();
        if(root == null) {
            root = node;
            root.key[0] = key;
            root.useSized++;
        }

        //根结点不为空，看看是否已经存在 key
        Pair<Node,Integer> find = find(key);
        if(find.getVal() != -1) {
            return;
        }

        //不存在该数值，需要进行插入
        Node cur = find.getKey();
        int i = cur.useSized - 1;
        for (; i >= 0; i--) {
            if(cur.key[i] > key) {
                cur.key[i+1] = cur.key[i];
            } else {
                break;
            }
        }
        cur.key[i+1] = key;
        cur.useSized++;

        if(cur.useSized == M) {
            split(cur);
        }

    }

    private void split(Node cur) {
        Node node = new Node();
        Node parent = cur.parent;
        int m = M / 2;

        //特殊：处理根节点的情况
        if(cur == root) {
            root = new Node();
            root.key[0] = cur.key[m];
            root.subs[0] = cur;
            root.subs[1] = node;
            root.useSized = 1;
            cur.parent = root;
            node.parent = root;
            return;
        }

        int i = 0;
        int j = m + 1;
        //拷贝key 和 subs
        while(j < M) {
            node.key[i] = cur.key[j];
            node.subs[i] = cur.subs[j];
            cur.subs[i] = null;//每次拷贝完，将原先区域置为空

            //如果拷贝过来的孩子结点不为空，需要修改孩子结点的双亲结点指向
            if(node.subs[i] != null) {
                node.subs[i].parent = node;
            }

            node.useSized++;
            i++;
            j++;
        }

        //多拷贝一次孩子
        node.subs[j] = cur.subs[i];

        //更新新结点的双亲结点
        node.parent = parent;

        //将中间值提到 cur 的双亲结点上去
        int midVal = cur.key[m];
        int end = parent.useSized-1;
        //移动双亲结点
        for(; end >= 0; end--) {
            if(parent.key[end] > midVal) {
                parent.key[end+1] = parent.key[end];
                parent.subs[end+2] = parent.subs[end+1];
            } else {
                break;
            }
        }

        parent.key[end+1] = midVal;
        //将当前父节点的孩子节点 新增为newNode
        parent.subs[end+2] = node;
        parent.useSized++;

        if(parent.useSized >= M) {
            split(parent);
        }

        cur.useSized -= 2;
    }

    //查找
    public Pair<Node,Integer> find(int key) {
        Node cur = root;
        Node prev = null;
        while(cur != null) {
            int i = 0;
            while (i < cur.useSized) {
                if(cur.key[i] == key) {
                    //存在
                    return new Pair<>(cur,i);
                } else if(cur.key[i] > key) {
                    //跳出本循环，进到孩子结点继续寻找
                    break;
                } else {
                    i++;
                }
            }
            prev = cur;
            cur = cur.subs[i];
        }
        return new Pair<>(prev,-1);
    }

}
